package traversal;

import sun.reflect.generics.tree.Tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class InOrderTraversal {
    private static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val)
        {
            this.val = val;
        }
    }

    class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {

            List<Integer> res = new ArrayList<>();
            if(root == null) return res;
            Stack<TreeNode> stack = new Stack<>();
            TreeNode node = root;
            while(!stack.isEmpty() || node != null)
            {
                while(node != null)
                {
                    stack.push(node);
                    node = node.left;
                }

                if(!stack.isEmpty()){
                    TreeNode pop = stack.pop();
                    res.add(pop.val);
                    node = pop.right;
                }
            }

            return res;

        }
    }

}